#include "triangulation.h"

#include <stdio.h>
#include <stdlib.h>

void test();

TriangleList * triangulation(PointList * pl, EdgeList * convexHull){
	TriangleList * tl = newTriangleList();
	Triangle * t;
	int i = 0;
	Triangle * ct;
	Triangle * foundTriangle;

	if(pl->length < MIN_POINTS){
		printf("Triangulation can be started only if there are more than 3 points.\n");
		return NULL;
	}
	t = findFirstTriangle(pl);

	addTriangle(tl, t);

	for(i = 0; i < tl->length; i++){
		ct = getTriangle(tl, i);

		//foundTriangle = findTriangle(ct->c, ct->a, ct->b, pl, convexHull);
		//if(foundTriangle != NULL && !containsTriangle(tl, foundTriangle))
		//	addTriangle(tl, foundTriangle);

		foundTriangle = findTriangle(ct->a, ct->b, ct->c, pl);
		if(foundTriangle != NULL && !containsTriangle(tl, foundTriangle))
			addTriangle(tl, foundTriangle);

		foundTriangle = findTriangle(ct->b, ct->c, ct->a, pl);
		if(foundTriangle != NULL && !containsTriangle(tl, foundTriangle))
			addTriangle(tl, foundTriangle);
	}

	//szukanie otoczki
	for(i = 0; i < tl->length; i++){
		ct = getTriangle(tl, i);

		findConvexHull(ct->a, ct->b, convexHull, tl);
		findConvexHull(ct->b, ct->c, convexHull, tl);
		findConvexHull(ct->c, ct->a, convexHull, tl);
	}

#ifdef DEBUG
	printTriangleList(tl);
#endif
	return tl;
}

Triangle * findFirstTriangle(PointList * pl){
	Triangle * t = newTriangle();
	int i = 2;
	Circle * c;

	t->a = pl->points[0];
	t->a->used = TRUE;

	t->b = pl->points[1];
	t->b->used = TRUE;

	while(isCoplanarWithPoints(t->a, t->b, pl->points[i]))
		i++;

	t->c = pl->points[i];
	t->c->used = TRUE;

	c = circumcircle(t);

	for(i = 0; i < pl->length; i++){
		if(!pl->points[i]->used){
			if(distance(pl->points[i], c->s) < c->r){
				t->c->used = FALSE;
				t->c = pl->points[i];
				t->c->used = TRUE;
				c = circumcircle(t);
				i = 0;
			}
		}
	}

	return t;
}

void findConvexHull(Point * a, Point * b, EdgeList * convexHull, TriangleList * tList){
	Edge * outerEdge = newEdge();
	if(countContainedEdges(tList, a, b) == 1){
		outerEdge->a = a;
		outerEdge->b = b;
		if(!containsEdge(convexHull, outerEdge)){
			addEdge(convexHull, outerEdge);
        }
	}
}

Triangle * findTriangle(Point * v, Point * a, Point * b, PointList * pl){
	Triangle * t = NULL;
	int hpWithVerticle, hpWithPoint, i, j;
	Circle * c;

	hpWithVerticle = halfPlane(v, a, b);

#ifdef DEBUG
	printf("hpWithVerticle=%d\n", hpWithVerticle);
#endif

	for(i = 0; i < pl->length; i++){
			hpWithPoint = halfPlane(pl->points[i], a, b);

#ifdef DEBUG
			printf("hpWithPoint=%d for i=%d\n", hpWithPoint, i);
#endif
			if(hpWithVerticle + hpWithPoint == 0){
				t = newTriangle();
				t->a = a;
				t->b = b;
				t->c = pl->points[i];
				t->c->used = TRUE;

				c = circumcircle(t);

#ifdef DEBUG
				printTriangle(t);
#endif
				for(j = 0; j < pl->length; j++){
					if(compare(pl->points[j], a) != 0 && compare(pl->points[j], b) != 0 && compare(pl->points[j], t->c) != 0)
						
						if(distance(pl->points[j], c->s) < c->r){
							t->c->used = FALSE;
							t->c = pl->points[j];
							t->c->used = TRUE;
							c = circumcircle(t);
							continue;
						}
					
				}
				break;
			}
	}

	return t;
}